namespace cpputils
{

template<class KTYPE, class COMP = less<KTYPE> >
class simple_heap : private noncopyable
{
public:
	struct node
	{
		KTYPE key;
		int index;
	};

	simple_heap()
		: Size(0)
	{
	}
	~simple_heap()
	{
		clear();
	}
	void set_key_comp(const COMP& SetComp)
	{
		Comp = SetComp;
	}
	bool empty() const
	{
		return Size == 0;
	}
	int size() const
	{
		return Size;
	}
	void clear()
	{
		for (int I = 0; I < Size; I++) delete Heap[I];
		Size = 0;
		reset_vector(Heap);
	}
	void reserve(int Capacity)
	{
		Heap.reserve(Capacity);
	}
	node* insert(const KTYPE& Key)
	{
		node* Node = new node;
		smart_ptr<node> NodeRes(Node);
		Node->key = Key;
		Node->index = Size;
		Heap.push_back(Node);
		NodeRes.release();
		Size++;
		update_up(Node->index);
		return Node;
	}
	void erase(const node* Node)
	{
		int Index = Node->index;
		KTYPE Key = Node->key;
		delete Node;
		if (Index < --Size)
		{
			Heap[Index] = Heap.back();
			Heap[Index]->index = Index;
			if (Comp(Heap[Index]->key, Key)) update_down(Index);
			else if (Comp(Key, Heap[Index]->key)) update_up(Index);
		}
		Heap.pop_back();
	}
	void update(node* Node)
	{
		update_down(Node->index);
		update_up(Node->index);
	}
	node* top() const
	{
		assert(Size > 0);
		return Heap[0];
	}

private:
	struct protected_node : private noncopyable
	{
		node** Heap;
		node* Node;
		const int& Index;

		protected_node(node** SetHeap, node* SetNode, const int& SetIndex)
			: Heap(SetHeap), Node(SetNode), Index(SetIndex)
		{}
		~protected_node()
		{
			Heap[Index] = Node;
			Node->index = Index;
		}
	};

	COMP Comp;
	int Size;
	vector<node*> Heap;

	void update_down(int Index)
	{
		node** P = begin_ptr(Heap);
		node* Node = P[Index];
		protected_node PNode(P, Node, Index);
		int Target;
		while (Target = Index + Index + 1, Target < Size)
		{
			if (Target + 1 < Size && Comp(P[Target]->key, P[Target + 1]->key)) Target++;
			if (!Comp(Node->key, P[Target]->key)) break;
			P[Index] = P[Target];
			P[Index]->index = Index;
			Index = Target;
		}
	}
	void update_up(int Index)
	{
		node** P = begin_ptr(Heap);
		node* Node = Heap[Index];
		protected_node PNode(P, Node, Index);
		while (Index != 0)
		{
			int Target = (Index - 1) >> 1;
			if (!Comp(P[Target]->key, Node->key)) break;
			P[Index] = P[Target];
			P[Index]->index = Index;
			Index = Target;
		}
	}
};

}
